#include<iostream>
#include<vector>
using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> f(n, vector<int>(3));
    auto g = f;
    f[0][1] = f[0][2] = g[0][1] = g[0][2] = -0x3f3f3f3f;
    f[0][0] = -prices[0];
    g[0][0] = 0;

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
            g[i][j] = g[i - 1][j];
            if (j-1>=0)
                g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
        }
    }
    return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));
}

int main()
{
    vector<int> nums = { 8,9,3,5,1,3 };
    maxProfit(nums);

    return 0;
}